﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;

namespace dst
{
    class Polynomial
    {
        Dictionary<int, Term> termsByDegree = new Dictionary<int, Term>();
        List<Term> terms = new List<Term>();
        static StreamWriter sw = new StreamWriter("D:/u.txt");

        /// <summary>
        /// s是1000001000101这种
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public static Polynomial Parse(string s)
        {
            Polynomial p = new Polynomial();

            for (int i = 0; i < s.Length; i++)
            {
                if (s[s.Length - i - 1] == '1')
                {
                    Term t = new Term("", i, 1);
                    p.BiInsert(t);
                }
                else if (s[s.Length - i - 1] == '0')
                {
                    ;
                }
            }
            return p;
        }

        public static Polynomial RandomP(int d)
        {
            Polynomial p = new Polynomial();
            Random r = new Random((int)DateTime.Now.ToBinary());

            for (int i = 0; i < d; i++)
            {
                if (r.Next(0, 2) == 1)
                {
                    Term t = new Term("", i, 1);
                    p.BiInsert(t);
                }
            }
            return p;
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="s"></param>
        /// <param name="d"></param>
        /// <returns></returns>
        public static Polynomial GenSymbPol(string s, int d)
        {
            Polynomial p = new Polynomial();
            for (int i = 0; i < d; i++)
            {
                Term t = new Term(s, i, i);
                p.BiInsert(t);
            }
            return p;
        }

        public static Polynomial GenNumePol(params int[] degs)
        {
            Polynomial p = new Polynomial();
            for (int i = 0; i < degs.Length; i++)
            {
                Term t = new Term("", degs[i], 1);
                p.BiInsert(t);
            }
            return p;
        }

        public int DegreeL
        {
            get { return terms[0].Degree; }
        }

        public int DegreeH
        {
            get { return terms[terms.Count - 1].Degree; }
        }

        private void BiInsert(Term t)
        {
            int begin = 0, end = terms.Count - 1;
            while (begin <= end)
            {
                int mid = (begin + end) / 2;
                if (t.Degree > terms[mid].Degree)
                {
                    begin = mid + 1;
                }
                else if (t.Degree < terms[mid].Degree)
                {
                    end = mid - 1;
                }
                else
                {
                    throw new Exception();
                }
            }
            terms.Insert(begin, t);
            termsByDegree.Add(t.Degree, t);
        }

        public void AddTerm(Term t)
        {
            BiInsert(t);
        }

        private void Add(Polynomial p)
        {
            for (int i = 0; i < p.terms.Count; i++)
            {
                Term t = p.terms[i];
                if (!termsByDegree.ContainsKey(t.Degree))
                {
                    BiInsert(t);
                }
                else
                {
                    Term term = termsByDegree[t.Degree];
                    term.Add(t);

                    if (term.IsEmpty())
                    {
                        terms.Remove(term);
                        termsByDegree.Remove(term.Degree);
                    }
                }
            }
        }

        private Polynomial Mul(Polynomial p)
        {
            Polynomial r = new Polynomial();
            for (int i = 0; i < p.terms.Count; i++)
            {
                Term t = p.terms[i];
                r += this.Mul(t);
            }

            return r;
        }

        private Polynomial Mul(Term t)
        {
            Polynomial r = new Polynomial();
            for (int i = 0; i < terms.Count; i++)
            {
                Term term = terms[i].Mul(t);
                r.BiInsert(term);
            }
            return r;
        }

        public Polynomial Mod(Polynomial irp, int degH, int degL)
        {
            Polynomial a = this.Clone();

            while (a.DegreeL < degL)
            {
                Polynomial tmp = new Polynomial();
                Term t = new Term(a.terms[0].Coeff, a.DegreeL - irp.DegreeL);
                tmp.BiInsert(t);

                Polynomial ol = irp * tmp;
                a.Add(ol);
            }

            while (a.DegreeH > degH)
            {
                Polynomial tmp = new Polynomial();
                Term t = new Term(a.terms.Last().Coeff, a.DegreeH - irp.DegreeH);
                tmp.BiInsert(t);

                Polynomial ol = irp * tmp;

                a.Add(ol);
            }

            return a;
        }

        /// <summary>
        /// 分解为矩阵，实际上这里是构造Mastrovito矩阵，
        /// </summary>
        /// <param name="es"></param>
        /// <returns></returns>
        public Matrix<Exp> FactorToMatrix(params Ele[] es)
        {
            Matrix<Exp> matrix = new Matrix<Exp>(es.Length);
            for (int i = 0; i < terms.Count; i++)
            {
                Term t = terms[i];
                AddExp<Exp> f = (AddExp<Exp>)t.Coeff.Factor(es);
                for (int j = 0; j < es.Length; j++)
                {
                    matrix[i, j] = f[j];
                }
            }

            return matrix;
        }

        /// <summary>
        /// 直接构造Mastrovito矩阵
        /// 因为已经知道构造方法，不用再乘再分解，直接用前一列下移位，相应位置+上一列最后一个元素即可
        /// </summary>
        /// <param name="irp"></param>
        /// <param name="shift"></param>
        /// <returns></returns>
        public static Matrix<Exp> FactorToMatrix(Polynomial irp, int shift)
        {
            int deg = irp.DegreeH;

            if (shift >= deg)
                throw new ArgumentOutOfRangeException();

            bool[] pos = new bool[deg];
            for (int i = 0; i < irp.terms.Count; i++)
            {
                if(irp.terms[i].Degree < deg)
                    pos[irp.terms[i].Degree] = true;
            }
            pos[0] = false;

            Matrix<Exp> matrix = new Matrix<Exp>(deg);
            for (int i = 0; i < deg; i++)
                matrix[i, shift] = Ele.GetEle("b", i);

            for (int j = shift - 1; j >= 0; j--)
            {
                for (int i = 0; i < deg - 1; i++)
                {
                    if (pos[i + 1])
                        matrix[i, j] = matrix[i + 1, j + 1] + matrix[0, j + 1];
                    else
                        matrix[i, j] = matrix[i + 1, j + 1];
                    matrix[i, j].SortSubs();
                }
                matrix[deg - 1, j] = matrix[0, j + 1];
            }

            for (int j = shift + 1; j < deg; j++)
            {
                matrix[0, j] = matrix[deg -1, j - 1];
                for (int i = 1; i < deg; i++)
                {
                    if (pos[i])
                        matrix[i, j] = matrix[i - 1, j - 1] + matrix[0, j];
                    else
                        matrix[i, j] = matrix[i - 1, j - 1];
                    matrix[i, j].SortSubs();
                }
            }

            return matrix;
        }

        /// <summary>
        /// 直接构造Toeplitz矩阵
        /// </summary>
        /// <param name="m"></param>
        /// <param name="irp"></param>
        /// <param name="s"></param>
        /// <returns></returns>
        public static Matrix<Exp> FactorToToeplitz(Matrix<Exp> m, Polynomial irp, int s)
        {
            if (m == null)
                return FactorToToeplitz(irp, s);

            else
            {
                for (int j = m.Order - 1; j > 0; j--)
                    m[0, j] = m[0, j - 1];
                for (int i = 0; i < m.Order - 1; i++)
                    m[i, 0] = m[i + 1, 0];
                m[m.Order - 1, 0] = m[0, 1];
                for (int i = 0; i < irp.terms.Count; i++)
                    if (irp.terms[i].Degree < m.Order && irp.terms[i].Degree > 0)
                        m[m.Order - 1, 0] = m[m.Order - 1, 0] + m[m.Order - irp.terms[i].Degree - 1, 0];
            }
#if DEBUG
            sw.WriteLine();
            sw.WriteLine("u*b");
            sw.WriteLine(m);
            sw.Flush();
#endif
            return m;
        }

        /// <summary>
        /// 直接构造Mastrovito矩阵，乘得Toeplitz矩阵
        /// </summary>
        /// <param name="irp"></param>
        /// <param name="s">shift</param>
        /// <returns></returns>
        public static Matrix<Exp> FactorToToeplitz(Polynomial irp, int s)
        {
            if (irp.terms.Count != 3 && irp.terms.Count != 5)
                throw new ArgumentException("invalid irreducible polynomial");

            Matrix<Exp> b = FactorToMatrix(irp, s);
            
            Matrix<Exp> u = new Matrix<Exp>(b.Order);
            if (Util.dicTransM.ContainsKey(irp))
                u = Util.dicTransM[irp];
            else
            {
                if (irp.terms.Count == 3)
                {
                    int shift = irp.terms[1].Degree;
                    for (int i = 0; i < b.Order - shift; i++)
                    {
                        u[i, i + shift] = Exp.Unit;
                    }
                    for (int i = 0; i < shift; i++)
                    {
                        u[b.Order - shift + i, i] = Exp.Unit;
                    }
                }
                else
                {
                    int shift = irp.terms[2].Degree;
                    int itvu = irp.terms[4].Degree - irp.terms[3].Degree;
                    int itvl = irp.terms[1].Degree - irp.terms[0].Degree;

                    int tidx = shift;

                    while (tidx <= u.Order)
                    {
                        Matrix<Exp> tmp = Matrix<Exp>.UShiftPower(u.Order, tidx);
                        u = u + tmp;
                        tidx += itvu;
                    }

                    tidx = shift;
                    while (tidx > 0)
                    {
                        Matrix<Exp> tmp = Matrix<Exp>.LShiftPower(u.Order, u.Order - tidx);
                        u = u + tmp;
                        tidx -= itvl;
                    }
                }
            }
#if DEBUG
            sw.WriteLine(irp.ToString("N"));
            sw.WriteLine();
            sw.WriteLine("b");
            sw.WriteLine(b);
#endif

            //b = u * b;  //here b is t
            b = u.Mul2Toep(b);
#if DEBUG
            sw.WriteLine("u");
            sw.WriteLine(u);
            sw.WriteLine("u*b");
            sw.WriteLine(b);
            sw.Flush();
#endif
            return b;
        }

        /// <summary>
        /// 分解成Toeplitz矩阵。
        /// 这个构造U的过程也可以优化，对于同一个不可约多项式的不同SPB，U是一致的
        /// </summary>
        /// <param name="irp"></param>
        /// <param name="es"></param>
        /// <returns></returns>
        public Matrix<Exp> FactorToToeplitz(Polynomial irp, params Ele[] es)
        {
            if (irp.terms.Count != 3 && irp.terms.Count != 5)
                throw new ArgumentException("invalid irreducible polynomial");

            Matrix<Exp> b = FactorToMatrix(es);
            //Matrix<Exp> b = FactorToMatrix(irp, );
            Matrix<Exp> u = new Matrix<Exp>(b.Order);

            if (irp.terms.Count == 3)
            {
                int shift = irp.terms[1].Degree;
                for (int i = 0; i < b.Order - shift; i++)
                {
                    u[i, i + shift] = Exp.Unit;
                }
                for (int i = 0; i < shift; i++)
                {
                    u[b.Order - shift + i, i] = Exp.Unit;
                }
            }
            else
            {
                int shift = irp.terms[2].Degree;
                int itvu = irp.terms[4].Degree - irp.terms[3].Degree;
                int itvl = irp.terms[1].Degree - irp.terms[0].Degree;

                int tidx = shift;

                while (tidx <= u.Order)
                {
                    Matrix<Exp> tmp = Matrix<Exp>.UShiftPower(u.Order, tidx);
                    u = u + tmp;
                    tidx += itvu;
                }

                tidx = shift;
                while (tidx > 0)
                {
                    Matrix<Exp> tmp = Matrix<Exp>.LShiftPower(u.Order, u.Order - tidx);
                    u = u + tmp;
                    tidx -= itvl;
                }
            }
#if DEBUG
            sw.WriteLine(irp.ToString("N"));
            sw.WriteLine();
            sw.WriteLine("b");
            sw.WriteLine(b);
#endif

            b = u * b;  //here b is t
#if DEBUG
            sw.WriteLine("u");
            sw.WriteLine(u);
            sw.WriteLine("u*b");
            sw.WriteLine(b);
#endif
            return b;
        }

        public static Polynomial operator +(Polynomial a, Polynomial b)
        {
            Polynomial r = a.Clone();
            r.Add(b);
            return r;
        }

        public static Polynomial operator *(Polynomial a, Polynomial b)
        {
            Polynomial r = a.Mul(b);
            return r;
        }

        public static Polynomial operator <<(Polynomial p, int n)
        {
            Polynomial r = (Polynomial)p.Clone();
            foreach (Term t in r.terms)
            {
                r.termsByDegree.Remove(t.Degree);
                t.Degree = t.Degree + n;
                r.termsByDegree.Add(t.Degree, t);
            }
            return r;
        }

        public static Polynomial operator >>(Polynomial p, int n)
        {
            Polynomial r = (Polynomial)p.Clone();
            foreach (Term t in r.terms)
            {
                r.termsByDegree.Remove(t.Degree);
                t.Degree = t.Degree - n;
                r.termsByDegree.Add(t.Degree, t);
            }
            return r;
        }

        public Polynomial Clone()
        {
            Polynomial p = new Polynomial();

            for (int i = 0; i < terms.Count; i++)
            {
                Term t = terms[i].Clone();
                p.terms.Add(t);
                p.termsByDegree.Add(t.Degree, t);
            }

            return p;
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < terms.Count; i++)
            {
                sb.Append(terms[terms.Count - i - 1].ToString() + "+");
            }
            string s = sb.ToString();
            if (s.Length > 0)
                s = s.Substring(0, s.Length - 1);

            return s;
        }

        public string ToString(string f)
        {
            return ToString(f, this.DegreeH, this.DegreeL);
        }

        public string ToString(string f, int h, int l)
        {
            if (f == "N")
            {
                StringBuilder sb = new StringBuilder();

                for (int i = DegreeH; i >= DegreeL; i--)
                {
                    if (termsByDegree.ContainsKey(i))
                        sb.Append(i + ",");
                }
                if (sb.Length > 1) ;
                sb.Remove(sb.Length - 1, 1);

                return sb.ToString();
            }
            else if(f == "B>")
            {
                StringBuilder sb = new StringBuilder();
                for(int i = h; i >= l; i--)
                {
                    if (termsByDegree.ContainsKey(i))
                        sb.Append("1");
                    else
                        sb.Append("0");
                }
                return sb.ToString();
            }
            else if(f == "B<")
            {
                StringBuilder sb = new StringBuilder();
                for (int i = l; i <= h; i++)
                {
                    if (termsByDegree.ContainsKey(i))
                        sb.Append("1");
                    else
                        sb.Append("0");
                }
                return sb.ToString();
            }
            else if(f == "B,>")
            {
                StringBuilder sb = new StringBuilder();
                for (int i = h; i >= l; i--)
                {
                    if (termsByDegree.ContainsKey(i))
                        sb.Append("1,");
                    else
                        sb.Append("0,");
                }
                if (sb.Length > 1)
                    sb.Remove(sb.Length - 1, 1);
                return sb.ToString();
            }
            else if (f == "B,<")
            {
                StringBuilder sb = new StringBuilder();
                for (int i = l; i <= h; i++)
                {
                    if (termsByDegree.ContainsKey(i))
                        sb.Append("1,");
                    else
                        sb.Append("0,");
                }
                if (sb.Length > 1)
                    sb.Remove(sb.Length - 1, 1);
                return sb.ToString();
            }
            else
                throw new NotImplementedException();
        }
    }
}
